package dataStructure.linearList.impl;

import dataStructure.collection.exception.IndexException;
import dataStructure.linearList.LinearList;
import dataStructure.linearList.node.Node;

import java.util.Arrays;

/**
 * @author guihuo (E-mail:1620657419@qq.com)
 * @version v1.0 创建时间：2017/10/28 2:07
 *          顺序表
 *          按照顺序存储方式存储的线性表，该线性表的结点按照逻辑次序存在在计算机一组连续的存储单元中。
 *          在插入和删除节点时，往往需要移动大量的数据
 *          如果表比较大，有时比较难分配足够的连续存续空间，往往导致内容分配失败，而无法存储。
 */
public class SequentialList<T> implements LinearList<T> {

    /**
     * 数据容器
     */
    private Node[] nodeList;

    /**
     * 当前数组最大长度
     */
    private int maxLength = 0;

    public SequentialList() {
        this.nodeList = new Node[3];
    }

    public SequentialList(int length) {
        this.nodeList = new Node[length];
    }

    @Override
    public int getLength() {
        return maxLength;
    }

    @Override
    @SuppressWarnings("unchecked")
    public T get(int index) {
        if (index < 0 || index >= maxLength) {
            throw new IndexException();
        }
        return (T) nodeList[index].getValue();
    }

    @Override
    @SuppressWarnings("unchecked")
    public int findIndex(T value) {
        if (value == null) {
            return -1;
        }
        for (int i = 0; i < getLength(); i++) {
            if (value.equals(nodeList[i].getValue())) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public void insert(T t) {
        insert(t, getLength());
    }

    @Override
    public void insert(T t, int index) {
        if (index < 0 || index > maxLength) {
            throw new IndexException();
        }
        int nodeListLength = nodeList.length;
        if (maxLength == nodeListLength) {
            Node[] newNodeList = new Node[(int) (nodeListLength * 1.5 + 1)];
            for (int i = 1; i <= nodeList.length; i++) {
                newNodeList[i] = nodeList[i - 1];
            }
            for (int i = 0; i < index; i++) {
                newNodeList[i] = newNodeList[i + 1];
            }
            nodeList = newNodeList;
        } else {
            for (int i = getLength(); i > index; i--) {
                nodeList[i] = nodeList[i - 1];
            }
        }
        nodeList[index] = new Node(t);
        maxLength++;
    }

    @Override
    public void delete(int index) {
        if (index < 0 || index >= maxLength) {
            throw new IndexException();
        }
        for (int i = index; i < maxLength; i++) {
            nodeList[i] = nodeList[i + 1];
        }
        nodeList[maxLength - 1] = null;
        maxLength--;
    }

    @Override
    public String toString() {
        return "SequentialList{" +
                "nodeList=" + Arrays.toString(nodeList) +
                ", maxLength=" + maxLength +
                '}';
    }
}
